package algorithm;

import java.util.*;
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {

    public static void main(String[] args) {

        System.out.println(new Solution().generateParenthesis(2));
    }

    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList<>();

        LinkedList<String> trace = new LinkedList<>();
        backTrace(n, trace, res);
        return res;
    }

    private void backTrace(int n, LinkedList<String> trace, ArrayList<String> res) {
        if(trace.size() == 2*n) {
            String result = trace.stream().reduce((a,b)->{return a+b;}).orElse("");
            res.add(result);
            return;
        }

        for(int i=0; i<n; i++) {
            trace.add("(");
            for(int j=0; j<n; j++) {
                trace.add(")");
            }
        }
        backTrace(n, trace, res);
        trace.removeLast();
    }
}